/*
 * Search for a Range
Given a sorted array of integers, find the starting and ending position of a given target value.

Your algorithm's runtime complexity must be in the order of O(log n).

If the target is not found in the array, return [-1, -1].

For example,
Given [5, 7, 7, 8, 8, 10] and target value 8,
return [3, 4].
 */
package com.xinpan.exercise;

public class SearchForARange {
    public int[] searchRange(int[] A, int target) {
        // Start typing your Java solution below
        // DO NOT write main() function
        int[] res = new int[2];
        res[0] = -1;
        res[1] = -1;
        
        if(A.length == 0)
            return res;
            
        int l = A.length-1;
        
        int s = 0;
        int e = l;
        int m = 0;

        while(s <= e)
        {
            m = (s+e)/2;
            if(A[m] < target)
                s = m+1;
            else if(A[m] > target)
                e = m-1;
            else
            {
                res[0] = m;
                e = m-1;
            }
        }
        
        s = 0;
        e = l;
        m = 0;
        while(s <= e)
        {
            m = (s+e)/2;
            if(A[m] < target)
                s = m+1;
            else if(A[m] > target)
                e = m-1;
            else
            {
                res[1] = m;
                s = m+1;
            }
        }
        
        return res;
    }
}
